//210 Course Schedule II
/*
给定 N 个课程和这些课程的前置必修课，求可以一次性上完所有课的顺序

输入输出样例
	输入是一个正整数，表示课程数量，和一个二维矩阵，表示所有的有向边（如 [1,0] 表示上
课程 1 之前必须先上课程 0）。输出是一个一维数组，表示拓扑排序结果

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
*/
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
	vector<vector<int>> graph(numCourses, vector<int>());
	vector<int> indegree(numCourses, 0), res;
	for (const auto & prerequisite : prerequisites) {
		graph[prerequisite[1]].push_back(prerequisite[0]);
		++indegree[prerequisite[0]];
	}
	queue<int> q;
	for (int i = 0; i < indegree.size(); ++i) {
		if (!indegree[i]) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		res.push_back(u);
		q.pop();
		for (auto v : graph[u]) {
			--indegree[v];
			if (!indegree[v]) {
				q.push(v);
			}
		}
	}
	for (int i = 0; i < indegree.size(); ++i) {
		if (indegree[i]) {
			return vector<int>();
		}
	}
	return res;

//1059
//1135
//882
